package ru.susu.algebra.ranks;

import java.lang.reflect.Array;
import java.math.BigInteger;
import java.util.BitSet;
import java.util.Date;
import java.util.HashMap;
import java.util.Map;

import org.apache.log4j.BasicConfigurator;
import org.apache.log4j.Logger;

import com.google.common.collect.Maps;

import ru.susu.algebra.number.MapPrimeNumbersProvider;
import ru.susu.algebra.number.PrimeNumbersProvider;

/**
 * @author akargapolov
 * @since: 11.03.2011
 */
public class FullDPRanksCounterNew
{
	private static Logger _log = Logger.getLogger("ranks");

	public static int NUMBER = 500;

	private static int MAX_NODES = 30 * 1000 * 1000;

	public static int DEPTH_SAVE = 4;

	private static Map<Integer, BitSet> _factors = new NumbersBitSetFactorizationProvider().performOperation(NUMBER);

	private static Map<Integer, Integer> _primes = new MapPrimeNumbersProvider().performOperation(NUMBER);

	private static int[][][] _dp = new int[NUMBER + 1][NUMBER + 1][4];

	private static Integer[] _sprimes = new PrimeNumbersProvider().performOperation(NUMBER);

	private static Map<BitSet, BigInteger>[][][] _data = (Map<BitSet, BigInteger>[][][])Array.newInstance(HashMap.class, NUMBER + 3, NUMBER + 3, 4);

	private static Map<BitSet, Object[]> _cache = Maps.newHashMap();//new LRUHashMap<BitSet, BitSet>(MAX_NODES / 10);
	private static Map<BigInteger, BigInteger> _intcache = Maps.newHashMap();//new LRUHashMap<BigInteger, BigInteger>(MAX_NODES / 10);

	private static long _nodes = 0;

	public static void main(String[] args) throws Exception
	{
		BasicConfigurator.configure();

		for (int i = 1; i <= NUMBER; i++)
		{
			Date start = new Date();
			BigInteger rank = recCounter(i, 1, 0, new BitSet(_primes.size()), 0);

			if (i % 10 == 0)
				System.gc();

			_log.info("rank[" + i + "] - " + rank);
			_log.info("nodes - " + _nodes);
			_log.info("total - " + Runtime.getRuntime().totalMemory() / 1000000);
			_log.info("free - " + Runtime.getRuntime().freeMemory()/ 1000000);
			_log.info("used - " + (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory())/ 1000000);
			_log.info("time - " + (new Date().getTime() - start.getTime()) + "ms");
			_log.info("BitsetCache size - " + _cache.size() + " IntCache size - " + _intcache.size());
		}
		_log.info("finished");
		Thread.sleep(120000);
	}

	private static int QUEUE_SIZE = NUMBER * NUMBER * 5;
	private static Object[] _queue = new Object[QUEUE_SIZE];
	private static int q1 = 0, q2 = 0;
	private static Map<String, Integer> _queueIndex = Maps.newHashMap();

	protected static BigInteger recCounter(int i, int k, int shift, BitSet bitset, int depth) throws Exception
	{
		if (_data[i][k][shift] == null)
			_data[i][k][shift] = Maps.newHashMap();

		BigInteger result = _data[i][k][shift].get(bitset);
		if (result != null)
		{
			return result;
		}
		result = BigInteger.ZERO;
		if (i == 0 && shift == 0)
		{
			if (!bitset.isEmpty())
				result = BigInteger.ONE;
		}
		else if (k <= i)
		{
			for (int j = k; j <= i; j += 2)
				if (recDP(i - j, j + 2, (shift + 1 - j + 4 * i) % 4) == 1)
				{
					BitSet tmp = (BitSet) bitset.clone();
					tmp.xor(_factors.get(j));
					result = result.add(recCounter(i - j, j + 2, (shift + 1 - j + 4 * i) % 4, tmp, depth + 1));
				}
		}

		if (depth % DEPTH_SAVE == 1 || DEPTH_SAVE <= 1)
		{
			_data[i][k][shift].put(getBitSet(bitset), getBigInteger(result));
			processCache(i, k, shift);
		}

		return result;
	}

	protected static void processCache(int i, int k, int shift)
	{
		String queueKey = getKey(i, k, shift);
		Integer index =_queueIndex.get(queueKey);
		if (index == null)
		{
			Integer[] tmp = new Integer[4];
			_queue[q2] = tmp;
			tmp[0] = i;
			tmp[1] = k;
			tmp[2] = shift;
			tmp[3] = 0;
			_queueIndex.put(queueKey, q2);
			index = q2;
			q2 = (q2 + 1) % QUEUE_SIZE;
		}
		((Integer[])_queue[index])[3]++;
		_nodes++;

		if (_nodes > MAX_NODES)
		{
			Integer[] tmp = (Integer[])_queue[q1];
			BitSet first = _data[tmp[0]][tmp[1]][tmp[2]].keySet().iterator().next();
			_data[tmp[0]][tmp[1]][tmp[2]].remove(first);
			decreaseBitSetAndWeak(first);
			_nodes--;
			tmp[3]--;
			if (tmp[3] == 0)
			{
				_queue[q1] = null;
				q1 = (q1 + 1) % QUEUE_SIZE;
				_queueIndex.remove(getKey(tmp[0], tmp[1], tmp[2]));
			}
		}
	}

	private static String DELIMITER = "_";

	private static String[][][] KEYS = new String[NUMBER][NUMBER][4];

	protected static String getKey(int i, int k, int shift)
	{
		if (KEYS[i][k][shift] == null)
		{
			KEYS[i][k][shift] = new StringBuilder().append(i).append(DELIMITER).append(k).append(DELIMITER).append(shift).toString();
		}
		return KEYS[i][k][shift];
	}

	private static int recDP(int n, int k, int shift)
	{
		if (n == 0)
		{
			if (shift == 0)
				return 1;
			else
				return -1;
		}
		if (k > n)
			return -1;
		if (_dp[n][k][shift] != 0)
			return _dp[n][k][shift];

		int res = -1;

		if (recDP(n - k, k + 2, (shift + 1 - k + 4 * 1000) % 4) == 1 || recDP(n, k + 2, shift) == 1)
			res = 1;

		_dp[n][k][shift] = res;
		return res;
	}

	protected static BitSet getBitSet(BitSet bitset)
	{
		Object[] result = _cache.get(bitset);
		if (result == null)
		{
			result = new Object[2];
			_cache.put(bitset, result);
			result[0] = bitset;
			result[1] = 0;
		}
		result[1] = (Integer) result[1] + 1;
		return (BitSet) result[0];
	}

	protected static void decreaseBitSetAndWeak(BitSet bitset)
	{
		Object[] result = _cache.get(bitset);
		if (result != null)
		{
			result[1] = (Integer) result[1] - 1;
			Integer value = (Integer) result[1];
			if (value == 0)
			{
				_cache.remove(bitset);
			}
		}
	}

	protected static BigInteger getBigInteger(BigInteger value)
	{
		BigInteger result = _intcache.get(value);
		if (result == null)
		{
			_intcache.put(value, value);
			result = value;
		}
		return result;
	}
}
